#include <iostream>
#include <vector>
using namespace std;

void heapify(vector<int>& nums, int largest, int n) {
    int index = largest;
    int left = largest * 2 + 1;
    int right = largest * 2 + 2;

    if (left < n && nums[left] > nums[index]) {
        index = left;
    }

    if (right < n && nums[right] > nums[index]) {
        index = right;
    }

    if (index != largest) {
        swap(nums[index], nums[largest]);
        heapify(nums, index, n);
    }
}

void build_heap(vector<int>& nums, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, i, n);
    }
}

void heap_sort(vector<int>& nums) {
    int n = nums.size();
    build_heap(nums, n);

    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, 0, i);
    }
}

int main() {
    vector<int> nums = {1, 8, 3, 5, 6, 7, 2, 4};
    heap_sort(nums);
    for (int n : nums) {
        cout << n << " ";
    }
    return 0;
}